﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Sol93
{
    IList<string> res = new List<string>();
    public  IList<string> RestoreIpAddresses(string s) { 

        

        DFS(s, 0,0);


        return res;
    }

    private void DFS2(string s, int startindex,int depth)//自己的写法
    {
        if (depth == 3)
        {
            res.Add(s);
            return;
        }

        int len = s.Length;
        for (int i = startindex; i < len; i++)
        {

            //添加.的操作

            //string head = s.Substring(0, i);
            //string nail= s.Substring(i, s.Length- i);
            //string newStr = head + "." + nail;
            //使用api
            //s.IndexOf(",", i, len);//在从i开始的长度为len的范围内找，
            string newStr = s.Insert(i, ".");

            Console.WriteLine(newStr);
            depth++;
            DFS2(newStr, i+1, depth);//传的是新串,加了一个.,index也加1


            //回溯
            depth--;
        }

    }private void DFS(string s, int startindex,int depth)//随想录
    {
        if (depth == 3)
        {//还要判断最后一个

           if(s.Length > 0 && startindex < s.Length)
            {
                if (isVaild(s, startindex, s.Length - 1))
                {
                    res.Add(s);

                }
            }

            
            return;
        }

        int len = s.Length;
        for (int i = startindex; i < len; i++)
        {
            //判断这一段子串（startindex到i合不合法的)
           if( isVaild(s, startindex, i))
            {
                string newStr = s.Insert(i+1, ".");

                Console.WriteLine("newStr:   " + newStr);



                depth++;
                DFS(newStr, i + 2, depth);//传的是新串
                                      //回溯
                depth--;
            }
            else
            {
                break;//说明有子串长度大于3，直接结束了
            }


            


            
        }

    }

    private bool isVaild(string s, int startindex, int curIndex)
    {

        if((curIndex - startindex + 1) > 3)
        {
            return false;
        }
        if (s[startindex] == '0' && startindex != curIndex)
        { // 0开头的数字不合法,除非只有一个0
            return false;
        }
        string child= s.Substring(startindex, curIndex- startindex+1);
        //Console.WriteLine("child:  "+child);
        //必须小于255
        if (int.Parse(child) < 0|| int.Parse(child) > 255)
        {
            return false;
        }
        return true;
    }
}
public class Program93
{

    static void Main93(string[] args)
    {
        //string s = "25525511135";
        //string s = "101023";
        string s = "0279245587303";
        //string s = "255";
        Sol93 sol = new Sol93();
        IList<string> res = sol.RestoreIpAddresses(s);
        for (int i = 0; i < res.Count; i++)
        {
            Console.WriteLine("res" + res[i]);
        }

        //for (int i = 0; i < 10; i++)
        //{
        //    if (i == 5)
        //    {
        //        //break;//直接结束
        //        continue;//跳过本次
        //    }
        //    else
        //    {
        //        Console.WriteLine(i);
        //    }
        //}
    }
}